package com.atues.backtrack.findSubsequences;

import com.alibaba.fastjson.JSON;

import java.util.*;

/**
 * @description:
 * @author: liang
 * @time: 2025-02-25 19:13
 */
public class Solution
{
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path =  new ArrayList<>();
//    Map<Integer, Boolean> map = new HashMap<>();用set更高效

    void backtracking(int[] nums , int start){
        if (path.size() >= 2) {
            res.add(new ArrayList<>(path));
        }
        Set<Integer> set = new HashSet<>();//这个set放这很有技术,这个set貌似村的就是数层上的数据
        //分析回溯逻辑，
        //对于序列，所有的数字都是连在一起的，如果有一个序列判断不满足那么其实以start开头的子序列就不可能满足，也就是以start的树枝就可以砍掉了
        for(int i = start ; i < nums.length ; i++){
            if(path.isEmpty() || nums[i] >= path.get(path.size() - 1)){
                if(set.contains(nums[i]) )//已经
                    continue;
                path.add(nums[i]);
                set.add(nums[i]);
                backtracking(nums,i+1);
                path.remove(path.size()-1);
//                set.remove(nums[i]);,这里set不用回溯,因为,如果你回溯的话树枝也会去重,
                //但如果不回溯,
            }
        }
    }
    public List<List<Integer>> findSubsequences(int[] nums) {
        backtracking(nums, 0);
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {4,6,7,7};
        List<List<Integer>> lists = solution.findSubsequences(nums);
        System.out.println(JSON.toJSONString(lists));
    }
}
